Many methods for sorting articles are known. Modern article sorting practice, especially sorting practice for items of mail, is based on the use of sorting machines. Many different sorting machines and methods for their use are known.
Typically, in the case of sorting mail, special purposes machines are used for sorting flats, which generally comprise: envelopes, particularly large envelopes; cards; and other generally flat items of mail. One example of a prior art sorting machine is the Muller-Martini flat sorter, which is well known in the art, many other sorters are also known in the art.
Some examples of apparatus and methods for mail sorting are described in the following U.S. patents:
U.S. Pat. No. 5,009,321 to Keough describes a multiple-pass sorting system for sorting mail pieces in accordance with a delivery order sequence. PA0 U.S. Pat. No. 5,054,602 to Kent et al describes a sorting system comprising a plurality of selectively dischargable sorting conveyors. PA0 U.S. Pat. No. 5,287,271 to Rosenbaum describes a data processing system for optimizing mail piece sorting using real time statistical data. PA0 U.S. Pat. No. 5,311,597 to Rosenbaum describes a method and system for active pigeon hole sorting of mail, including elimination of pigeon holes for those not receiving mail on a particular day. PA0 U.S. Pat. No. 5,421,464 to Gillmann et al describes a method for sequencing parcels, including a sorting plan in which overfilling of individual stacking compartments is avoided. PA0 U.S. Pat. No. 5,547,063 to Bonnet describes a sorting system for high speed sorting of packages, including a feeding mechanism, a conveying system, and ejection modules. PA0 U.S. Pat. No. 5,667,078 to Walach describes an apparatus and method for mail sorting, including generating a first sequence number for each subset of mail, sorting the first subset into batches according to the first sequence number, associating one ofthe first sequence numbers corresponding to the destination addresses of the mail items in the first subset, generating a second sequence number, sorting the second subset into batches according to the second and first sequence numbers while disregarding N of the most significant digits of the first sequence number, interleaving the batches from the first and the second subset, and sorting according to the N most significant digits of the first sequence number. The method is intended to allow porting of the mail to begin prior to all the mail being physically present at the sorter. PA0 U.S. Pat. No. 5,770,841 to Moed et al describes a system and method for reading package information, the system including an imaging system and a label decoding system.
FIG. 1 comprises a simplified block diagram illustration of a typical prior art item sorter, also termed herein an article sorter; typical item sorters include sorters intended for items of mail, which are known by various terms including: a mail sorter, a sorting machine, a mail sorting machine, and a flat sorting machine. In state-of-the art sorters a first plurality of input bins 10 is provided, comprising in the example of FIG. 1, P input bins. Typically, items such as flats are pre-coded, either by the sender or in a pre-processing step, with a bar code signifying the destination of the item, typically but not necessarily represented as an integer code, such as a mail carrier route code. The items are then placed, in arbitrary groups, into each of the P input bins 10.
Items from each of the P input bins 10 are fed to a Programmable Sorting Mechanism 20. Typically, the Programmable Sorting Mechanism 20 is operative to sort input items placed in any of the P input bins 10 in accordance with all or a portion of the bar-coded destination code; the portion of the destination code used for sorting is generally programmable by an operator of the sorter. The Sorting Mechanism 20 typically reads the bar codes and distributes the items received from the P input bins 10 into a second plurality of output bins 30, shown in FIG. 1 as N output bins, according to the programmed portion of the bar code on each item.
Item sorters such as the item sorter of FIG. 1 are operative to arbitrarily combine the input from each of the P input bins 10 during sorting, such that no distinction is made by the Sorting Mechanism 20 based on the particular input bin 10 from which an item is fed to the Sorting Mechanism 20. In other words, items from any or all of the P input bins 10 may be sorted into any or all of the N output bins 30; it will be appreciated by persons skilled in the art that this common property of item sorters limits the type of sorting method which can be successfully used with such an item sorter.
Generally in item sorters, the number of output bins 30, N, is at least equal to, and is usually significantly greater than, the number of input bins 10, P. Even if there are a relatively large number of output bins 30, N, often it is desirable to sort the output into more categories than the number of output bins 30, N, such as, for example, if the number of different carrier routes is greater than the number of output bins 30, N.
The problem of sorting items by distributing the items into categories or piles, where the number of piles is small relative to the number of desired categories or possible sorting keys, is well-known. One reference describing known methods for such sorting is Knuth, The Art of Computer Programming Vol. 3, "Searching and Sorting", 1973 edition, pages 170-171, 177, 379-380, and 384. Knuth describes distribution sorting, also known as radix sorting, which is very well known in the art and is known in the art of mail sorting. The terms "distribution sorting" and "radix sorting" will be used interchangeably throughout the present specification and claims. As described by Knuth, radix sorting consists of least significant digit radix sorting, which begins at the least significant digit of a sorting key; and most significant radix sorting, which begins at the most significant digit of a sorting key. In both types of radix sorting, sorting proceeds linearly through the entire sorting key in the direction implied by the choice of beginning digit.
Radix sorting of items having an associated sorting code, such as a destination code or carrier route code, may be performed with any convenient base or radix, the radix being chosen based on characteristics such as, for example, number of input and output bins, of the sorting machine being used or, in the case of sorting inside a computer program, on program and memory requirements.
By way of example only, consider a radix sorting method for using a sorter having one input bin and 10 output bins to sort items having up to 1000 distinct sorting codes ranging from 000 to 999. The items are first input into the input bin and sorted according to least significant digit. The resulting output in the 10 output bins is then stacked in order, from sorted digit 0 to 9, and placed in the input bin again. In a second pass, the items are sorted according to the second-least-significant digit. The resulting output in the 10 output bins is then stacked in order, from most recently sorted digit 0 to 9, and placed in the input bin again. Finally, a third sorting pass is performed based on the third-least-significant, or most significant, digit. The resulting output in the 10 output bins is again stacked in order, from sorted digit 0 to 9.
It will be appreciated, as is well known in the art, that the radix sorting method described above is a reasonably efficient and well-known method which is well suited to item sorters with a single input bin. Unfortunately, although the method can be performed at maximum efficiency with multiple input bins in the first pass, only a single input bin can be used for subsequent passes, since the input from the plurality of input bins 10 is treated in a single integrated pass by the Sorting Mechanism 20, as previously described. For this reason, radix sorting is inefficient when used with an item sorter having a plurality of input bins, since some input bins are unused after the first pass.
It is also known to perform radix sorting from most significant digit to least significant digit, and use of this method is known, particularly in a geographically distributed manner, in mail systems where mail is first sorted by region, or most significant digit, then by postal area, or next most significant digit, and so on. After mail has been distributed to an individual mail sorting center it is known to then sort mail by methods such as those described above.